package hot_problems_100;

public class P8_0003 {
    /*
    * 求最长的无重复子串的长度，字符集为ASCII码
    * s.length <= 50000
    * */

    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        int[] indices = new int[128];
        for(int i=0; i<128; i++) indices[i] = -1;
        int cur_len = 0;
        int min_index = 0;
        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            int last_index = indices[c];
            if(last_index>=min_index){
                cur_len = i-last_index;
                min_index = last_index+1;
                /*  直接整理哈希表速度过慢，不如直接记录左边界位置
                for(int j=0; j<128; j++){
                    if(indices[j] <= last_index){
                        indices[j] = -1;
                    }
                } */
            } else {
                cur_len ++;
            }
            res = Math.max(res, cur_len);
            indices[c] = i;
        }
        return res;
    }
}
